//给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 
//
// 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： 
//
// 
// "123" 
// "132" 
// "213" 
// "231" 
// "312" 
// "321" 
// 
//
// 给定 n 和 k，返回第 k 个排列。 
//
// 说明： 
//
// 
// 给定 n 的范围是 [1, 9]。 
// 给定 k 的范围是[1, n!]。 
// 
//
// 示例 1: 
//
// 输入: n = 3, k = 3
//输出: "213"
// 
//
// 示例 2: 
//
// 输入: n = 4, k = 9
//输出: "2314"
// 
// Related Topics 数学 回溯算法 
// 👍 307 👎 0

package leetcode.editor.cn;

import java.util.Iterator;
import java.util.Stack;

//Java：第k个排列
public class P60PermutationSequence {

    /**
     *
     * 思路：回溯算法，参考第46题全排列。 排列出来的就是按顺序的，所以只要记录生成了几个，第k个结束后退出就行了
     *
     * 执行用时： 754 ms , 在所有 Java 提交中击败了 18.13% 的用户 内存消耗： 37.2 MB , 在所有 Java 提交中击败了 83.05% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int total = 0;
        private String result = "";

        public String getPermutation(int n, int k) {
            int[] nums = createNums(n);
            boolean[] used = new boolean[n];
            dfs( n, k, nums, used, new Stack<>());
            return result;
        }

        // 全排列
        private void dfs(int n, int k, int[] nums, boolean[] used, Stack<Integer> path) {
            if (total == k) {
                return;
            }

            // 路径里面的数字是n个，代表是正确的全排列
            if (path.size() == n) {
                total++;
                if (total == k) {
                    Iterator<Integer> it = path.iterator();
                    StringBuilder sb = new StringBuilder("");
                    while (it.hasNext()) {
                        Integer a = it.next();
                        sb.append(a);
                    }
                    result = sb.toString();
                }
                return;
            }
            for (int start = 0; start < n; start++) {
                if (total == k) {
                    return;
                }
                // start之前用过的话，就取下一个，不然数字会重复使用
                if (used[start]) {
                    continue;
                }
                path.push(nums[start]);
                used[start] = true;
                dfs(n, k, nums, used, path);
                used[start] = false;
                path.pop();
            }

        }

        private int[] createNums(int n) {
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = i + 1;
            }
            return nums;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P60PermutationSequence().new Solution();
        String s = solution.getPermutation(9, 353955);
        System.out.println(s);
        // TO TEST
    }

}